/**
 * 
 */
package leetCode;

import java.util.HashMap;

/**
 * @author zhong
 *
 */
public class ParseLispExpression {
	public int evaluate(String expression) {
		HashMap<Integer, Integer> leftRightPa = new HashMap<>();
		return evaluate(expression, leftRightPa, new HashMap<String, Integer>(), new int[] { 0 });
	}

	private int evaluate(String expression, HashMap<Integer, Integer> leftRightPa, HashMap<String, Integer> hashMap,
			int[] i) {
		char ch = expression.charAt(i[0]);
		int end = i[0] + 1;
		while (end < expression.length() && expression.charAt(end) != ' ' && expression.charAt(end) != ')') {
			end++;
		}
		String string = expression.substring(i[0], end);
		if (string.equals("(let")) {
			// 可能要修改变量，先复制map
			HashMap<String, Integer> inner = new HashMap<>(hashMap);
			boolean getVar = false;
			i[0] = end + 1;
			while (true) {
				// 获取变量
				if (expression.charAt(i[0]) == '(') {// 是最后需要的exp而不是被赋值的变量
					break;
				}
				end = i[0] + 1;
				while (expression.charAt(end) != ')' && expression.charAt(end) != ' ') {// 最后结尾可能是右括号
					end++;
				}
				if (expression.charAt(end) == ')') {// 右括号代表这个变量、数值是要返回的exp
					string = expression.substring(i[0], end);// !!!!!!不要忘了更新str
					getVar = true;
					break;
				}
				string = expression.substring(i[0], end);
				i[0] = end + 1;// 跳过var后面的空格

				// 获取expression
				int e = evaluate(expression, leftRightPa, inner, i);// ！！！！！注意要是inner
				// 如果expression是变量或者数字，则有空格，需要再跳过
				inner.put(string, e);
				// 跳过空格
				i[0]++;
			}

			// 获取let的expression
			if (getVar) {
				i[0] = end + 1;// skip )
				if (Character.isLetter(string.charAt(0))) {// variable or integer
					return inner.get(string);
				} else {
					return Integer.parseInt(string);
				}
			} else {
				int e = evaluate(expression, leftRightPa, inner, i);
				i[0] += 1;// skip ) and space
				return e;
			}
		} else if (string.equals("(add") || string.equals("(mult")) {// (add x y)
			i[0] = end + 1;// 跳过空格
			int e1 = evaluate(expression, leftRightPa, hashMap, i);
			i[0]++;// skip space
			int e2 = evaluate(expression, leftRightPa, hashMap, i);
			i[0] += 1;// skip )
			if (string.equals("(add")) {
				return e1 + e2;
			} else {
				return e1 * e2;
			}
		} else if (Character.isLetter(ch)) {// 变量
			i[0] = end;// reach to space or )
			return hashMap.get(string);
		} else {// 正负数
			i[0] = end;// reach to space or )
			return Integer.parseInt(string);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] strings = { "(let x 7 -12)", "(let x 2 (mult (let x 3 y 4 (add x y)) x))", "(add 1 2)",
				"(mult 3 (add 2 3))", "(let x 2 (mult x 5))", "(let x 2 (mult x (let x 3 y 4 (add x y))))",
				"(let x 3 x 2 x)", "(let x 1 y 2 x (add x y) (add x y))", "(let x 2 (add (let x 3 (let x 4 x)) x))",
				"(let a1 3 b2 (add a1 1) b2)" };
		ParseLispExpression parseLispExpression = new ParseLispExpression();
		for (String string : strings) {
			System.out.println(parseLispExpression.evaluate(string));
		}
	}

}
